/*
有一个货箱容量为78立方米，同时有 12件物品，体积分别为1.75、5.65、4.8、2.2、1.6、3.45、6.68、5.12、0.19、1.46、8.2、2.7。
现在从12件物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。请编写一个C程序，给出装载方案，输出这个最小值。
*/

#include <stdio.h>
#define VOLUME 78 // 货箱容积
#define SIZE 12   //有12件物品
int main()
{
	//各个物品的体积
	float arrVolumes[SIZE] = {1.75, 5.65, 4.8, 2.2, 1.6, 3.45, 6.68, 5.12, 0.19, 1.46, 8.2, 2.7};
	float maxV = 0;               //装入物品最大的体积
	unsigned bitSolutionBest = 0; //方案
	unsigned bitSolution = 0;     //当前的装载方案，低12位对应是否装入该物品。bit等于1表示装载该物品，等于0则不装载该物品
	for (bitSolution = 0; bitSolution <= 0xFFF; bitSolution++)
	{
		//分别尝试当前装载方案的效果
		float tmpV = 0;
		for (int i = 0; i < SIZE; i++)
		{
			tmpV += arrVolumes[i] * (bitSolution & (1 << i) /*取对应的bit*/);
		}
		if (tmpV > maxV && tmpV <= VOLUME)
		{
			maxV = tmpV;
			bitSolutionBest = bitSolution;
			printf("当前最好的装载方案为%x，最小剩余空间为：%.2f\n", bitSolutionBest, VOLUME - maxV);
		}
	}
}
